
#ifndef _ORDEREDLIST_H_
#define _ORDEREDLIST_H_

#include "lib.h"

template <class C> class COrderedList
{
	public:
		COrderedList(bool8 delete_data = true);
		virtual ~COrderedList();

		COrderedList(COrderedList *list);

		uint32 GetNum();
		C *GetAt(uint32 index);

		C *GetFirst(void **handle);
		C *GetNext(void **handle);

		bool8 Add(C *data);
		bool8 Remove(C *data);

		bool8 AddAfter(void *handle, C *data);

		void Swap(void *loc1, void *loc2);

		void DestroyAll();
	protected:

		C *RemoveNoDelete(C *data);

	protected:
		bool8 m_delete_data;
		uint32 m_number;

		struct ListNode
		{
			C *data;
			ListNode *next;
		};

		ListNode *m_head;
		ListNode *m_tail;
};

template <class C> COrderedList<C>::COrderedList(bool8 delete_data)
{
	m_delete_data = delete_data;
	m_number = 0;
	m_head = (ListNode *)0;
	m_tail = (ListNode *)0;
}

template <class C> COrderedList<C>::COrderedList(COrderedList *list)
{
	m_number = 0;
	m_head = (ListNode *)0;
	m_tail = (ListNode *)0;
	m_delete_data = list->m_delete_data;

	void *handle;
	C *curr;

	curr = list->GetFirst(&handle);

	while(handle)	
	{
		Add( new C(*curr) );
		curr = list->GetNext(&handle);
	}
}

template <class C> COrderedList<C>::~COrderedList()
{
	DestroyAll();
}

template <class C> inline C *COrderedList<C>::GetFirst(void **handle)
{
	*handle = (void *)m_head;
	if(*handle)
		return ((ListNode *)(*handle))->data;
	else
		return (C *)0;
}

template <class C> inline C *COrderedList<C>::GetNext(void **handle)
{
	*handle = (void *)(((ListNode *)(*handle))->next);
	if(*handle)
		return ((ListNode *)(*handle))->data;
	else
		return (C *)0;
}

template <class C> inline void COrderedList<C>::DestroyAll()
{
	ListNode *next;
	while(m_head)
	{
		next = m_head->next;

		if(m_delete_data)
		{
			delete m_head->data;
		}
		m_head->data = (C *)0;

		delete m_head;
		m_head = next;

		if(m_head)
			next = m_head->next;
	}

	m_number = 0;
	m_head = (ListNode *)0;
	m_tail = (ListNode *)0;
}

template <class C> inline uint32 COrderedList<C>::GetNum()
{
	return m_number;
}

template <class C> inline C *COrderedList<C>::GetAt(uint32 index)
{
	if(index >= m_number) 
	{
		return (C *)0;
	}
	else
	{
		ListNode *curr;
		curr = m_head;

		uint32 count = 0;

		while(count < index)
		{
			count++;
			if(curr)
			{
				curr = curr->next;
			}
			else
			{
				return (C *)0;
			}
		}

		return curr->data;
	}
}

template <class C> inline bool8 COrderedList<C>::Add(C *data)
{
	if(!m_head)
	{
		// first one
		m_head = new ListNode();
		if(!m_head)
		{
			return false;
		}

		m_head->next = (ListNode *)0;
		m_head->data = data;

		m_tail = m_head;

		m_number++;
	}
	else
	{
		m_tail->next = new ListNode();
		if(!m_tail->next)
		{
			return false;
		}

		m_tail = m_tail->next;

		m_tail->next = (ListNode *)0;
		m_tail->data = data;
		m_number++;
	}

	return true;
}

template <class C> inline void 
COrderedList<C>::Swap(void *loc1, void *loc2)
{
	ListNode *node1 = (ListNode *)loc1;
	ListNode *node2 = (ListNode *)loc2;

	C *temp = node1->data;

	node1->data = node2->data;
	node2->data = temp;
}

template <class C> inline bool8 
COrderedList<C>::AddAfter(void *handle, C *data)
{
	ListNode *node = (ListNode *)handle;

	ListNode *newnode = new ListNode();

	if(!newnode)
	{
		return false;
	}

	newnode->data = data;

	if(!handle)
	{
		newnode->next = m_head;
		m_head = newnode;

		if(!m_tail)
			m_tail = newnode;
	}
	else if(node && node->next)
	{
		// interior to the list 
		newnode->next = node->next;
		node->next = newnode;
	}
	else
	{
		// last one in list
		m_tail->next = newnode;

		newnode->next = (ListNode *)0;

		m_tail = newnode;
	}

	m_number++;

	return true;
}

template <class C> inline bool8 COrderedList<C>::Remove(C *data)
{
	// find the entry
	ListNode *curr = m_head;
	ListNode *prev = (ListNode *)0;

	while(curr && (curr->data != data)) 
	{
		prev = curr;
		curr = curr->next;
	}

	if(curr)
	{
		if(prev)
		{
			if(m_tail == curr)
				m_tail = prev;

			prev->next = curr->next;
			if(m_delete_data)
			{
				delete curr->data;
			}
			curr->data = (C *)0;
			delete curr;
			m_number--;
		}
		else
		{
			// first one in the list
			prev = m_head;

			// only one in the list..
			if(m_tail == m_head)
			{
				m_tail = (ListNode *)0;
			}

			m_head = m_head->next;
			if(m_delete_data)
			{
				delete prev->data;
			}
			prev->data = (C *)0;

			delete prev;
			m_number--;
		}

		return true;
	}
	else
	{
		return false;
	}
}

#endif






